package algocasts;

import brinaryTree.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class P119_SubtreeOfAnotherTree {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

    }

    private boolean isSameTree(TreeNode p, TreeNode q) {

        if (p == null && q == null) return true;
        else if (p == null || q == null) return false;
        else if (p.val != q.val) return false;
        else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
    // Time: O(m*n)  Space: O(h)
    public boolean isSubtree(TreeNode s, TreeNode t) {
        if (t == null) return true;
        if (s == null) return false;
        return isSameTree(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    }

    private Map<TreeNode, Integer> map = new HashMap<>();

    private String computeHash(TreeNode t) {
        if (t == null) return "#";
        String left = computeHash(t.left);
        String right = computeHash(t.right);
        String hash = left + t.val + right;
        map.put(t, hash.hashCode());
        return hash;
    }

    private boolean isSub(TreeNode s, TreeNode t) {
        if (t == null) return true;
        if (s == null) return false;
        return map.get(s).equals(map.get(t)) || isSub(s.left, t) || isSub(s.right, t);
    }

    // Time : O(m+n), Space: O(h)
    public boolean isSubtree_Hash(TreeNode s, TreeNode t) {
        computeHash(s);
        computeHash(t);
        return isSub(s, t);
    }


}
